package com.leo.m1802.d05;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by LEO on 2018/2/5.
 */
public class BinaryTree<T> {
    private Node<T> root;

    class Node<T>{
        T key;
        Node<T> left,right;

        public Node() {
        }

        public Node(T key) {
            this.key = key;
        }

        public Node(T key, Node<T> left, Node<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }
    }

    void visit(Node<T> node){
        System.out.print(node.key+"  ");
    }

    public void preOrder(){
        preOrder(root);
    }

    public void preOrder(Node<T> n){
        if (n != null){
            visit(n);
            preOrder(n.left);
            preOrder(n.right);
        }
    }

    public void midOrder(Node<T> n){
        if (n != null){
            midOrder(n.left);
            visit(n);
            midOrder(n.right);
        }
    }

    public void postOrder(Node<T> n){
        if (n != null){
            postOrder(n.left);
            postOrder(n.right);
            visit(n);
        }
    }

    public void preOrder2(Node<T> n){
        Deque<Node<T>> stack = new LinkedList<Node<T>>();
        Node<T> t = n;
        while (t != null || !stack.isEmpty()){
            while (t != null){
                visit(t);
                stack.push(t);
                t = t.left;
            }
            if (!stack.isEmpty()){
                t = stack.poll();
                t = t.right;
            }
        }
    }

    public void midOrder2(Node<T> n){
        Deque<Node<T>> stack = new LinkedList<Node<T>>();
        Node<T> t = n;
        while (t != null || !stack.isEmpty()){
            while (t != null){
                stack.push(t);
                t = t.left;
            }
            if (!stack.isEmpty()){
                t = stack.poll();
                visit(t);
                t = t.right;
            }
        }
    }

    public void levelOrder(Node<T> n){
        if (n == null){ return;}
        Queue<Node<T>> queue = new LinkedList<>();
        queue.offer(n);
        Node<T> t;
        while (!queue.isEmpty()){
            t = queue.poll();
            visit(t);
            if (t.left != null){ queue.offer(t.left); }
            if (t.right != null){ queue.offer(t.right); }
        }
    }
}
